1. Field of the Invention
This invention relates to three-dimensional graphics processing.
2. Background
In general, three-dimensional (3D) graphics applications display 3D objects in a two-dimensional (2D) space (e.g., a display screen). The pixels in a 2-dimensional graphic have the properties of position, color, and brightness. On the other hand, a 3D pixel adds a depth property that indicates where the point lies on an imaginary Z-axis. Texture is created as 3D pixels are combined, each with its own depth value.
Converting information about 3D objects into a bit map that can be displayed is known as rendering, and requires considerable memory and processing power. In the past, 3D graphics was available only on powerful workstations, but now 3D graphics accelerators are commonly found in personal computers (PC). The graphics accelerator contains memory and a specialized microprocessor to handle many of the 3D rendering operations. Open GL® (Open Graphics Library) for desktops defines an application programming interface (API) for writing applications that produce 3D and 2D computer graphics. The API includes hundreds of functions for drawing complex three-dimensional scenes from primitives.
User-defined clip planes permit for efficient early culling of non-visible polygons—increasing performance and saving power. The user-defined clipping is usually done in hardware in the PC graphics systems. It is relatively a new feature in handheld devices. OpenGL® ES is a subset of the desktop OpenGL which creates an interface between software and graphics. Furthermore, user-defined clipping is either done in software or in hardware in mobile phones. If user-defined clipping is done in software, user-defined clipping is usually done in eye coordinates. Vertices (vertex coordinates) are first transformed from object space into eye space. The transformed vertices are tested against the user-defined clipping planes in eye space. Vertices are assembled into primitives. If a primitive partially lies in the half-space of a clipping plane, the primitive will be clipped by the clipping plane. However, numerous computations are needed to transform the numerous vertices from the object space to the eye space.
For example, in 3D graphics applications, such as OpenGL® ES or OpenGL®, a user can specify multiple clipping planes. A clipping plane is an arbitrary plane in 3D space. Each plane defines a half-space. Any object or any portion of the object will be clipped if it does not lie in the half-space. Any object in the scene will be tested against all the clipping planes. This process is called user-defined clipping. Another type of clipping is called frustum clipping that clips objects against the eye frustum. Frustum clipping will not be described herein.
A current challenge is to implement the user-defined clipping using a 3D software engine found in a hand-held 3D imaging device without poor performance. The hand-held 3D imaging devices have limited battery power and processing capability. A significant number of computations are needed to transform a lot of vertices from the object space to the eye space, these computations reduce the performance of the 3D imaging device.
In a conventional user-defined clipping process in eye space shown in FIG. 1, such as provided by the OpenGL® ES engine, the vertex object coordinates, denoted as V_obj, of step S22 are transformed using a modelview transformation process at step S24. At step S24 the vertex object coordinates V_obj are converted into eye space to form vertex eye coordinates, denoted as V_eye, where the vertex object coordinates V_obj are multiplied by the modelview matrix M for the coordinates. The vertex eye coordinates V_eye are subjected to primitive assembling at one of steps S28 (if a polygon), S30 (if a line segment) and S32 (if a point). The primitive assembling for a polygon at step S28 and for a line segment at step S30 are further subjected to a flat shading process at step S34. If the shade model is flat shading, then the color of each vertex will be replaced with the color of the last vertex of the triangle or line. The output from the flat shading process of step S34 or the point assemble process of step S32 are subjected to the user-defined clipping process in eye space at step S40, if enabled. Enabling the clipping process at step S40 will be described in detail later.
The primitives can be a polygon, a line segment or point and can be clipped using a conventional user-defined clipping process shown in FIG. 1. These primitives can be clipped against a user clip plane at step S40. In clip coordinates, the view volume of step S44 is defined by−wc≦xc≦wc −wc≦yc≦wc −wc≦zc≦wc where xc, yc and zc are clip coordinates.
The view volume can be further restricted by as many as n user-defined clip planes to generate the clip volume wherein n is an implementation dependent. Each user-defined plane specifies a half-space. The clip volume is the intersection of all such half-spaces with the view volume (Step S44). It should be noted that in ordinary OpenGL, user clipping can be done in either eye space or in the projection space. However, step S44 assumes that it is done in projection space. However, if no user-defined clip planes are enabled at step S38, the clip volume is the view volume at step S44. Hence, the output from the Flat shading process S34 (if the primitive is a polygon or a line segment) or the point assemble process of step S32 are subjected to a projection transform at step S42 without the user-defined clipping process of step S40.
A user-defined clip plane is specified at step S12 with the functionClipPlane(plane,eqn[4])where the value of the first argument, plane, is a symbolic constant, CLIP_PLANEi, where i is an integer between 0 and n−1, indicating one of n user-defined clip planes; and eqn[4] is an array of four single-precision floating-point values. (OpenGL® requires double precision floating points.) The four single-precision floating-point values are the coefficients of a plane equation P of step S14 in object coordinates, denoted as p1, p2, p3 and p4. The current modelview matrix, denoted as Mc, is stored for the clip plane P at step S18. The inverse of the current modelview matrix Mc for the clip plane P is obtained or calculated at step S20 via an inverse matrix process. The resultant inverse matrix is denoted as Inv_Mc. The Inv_Mc is applied to these coefficients via multiplication, at the time they are specified at step S16, yielding P_eye as follows:P—eye=(p′1p′2p′3p′4)=(p1p2p3p4)Mc−1 where Mc is the current modelview matrix; Mc−1 is the Inv_Mc; the resulting plane equation is undefined if Mc is singular and may be inaccurate if Mc is poorly-conditioned; and P_eye is the plane equation coefficients in eye coordinates at step S16 which is followed by step S40. At step S40, all points with eye coordinates (xe ye ze we)T that satisfyP—eyeT*V—eye>=0 or(p′1*xe+p′2*ye+p′3*ze+p′4*we)>=0lie in the half-space defined by the plane; points that do not satisfy this condition do not lie in the half-space where T is a transpose; and * denotes multiplication of a matrix or vector.
At step S36, the user-defined clip planes are enabled with an Enable command. Alternately, the clipping could be disabled with the Disable command. At step S38, a determination is made whether the user-defined clip planes are enabled or disabled. If the determination is “YES” (meaning enabled), the output from the flat shading process S34 (if a polygon or line segment assemble of step S28 or S30) or the point assemble process S32 is subject to clipping at step S40 in eye space. The value of the argument to either command is CLIP_PLANEi where i is an integer between 0 and n; specifying a value of i enables or disables the plane equation with index i. The constants obey ClipPlane I=ClipPlane0+i.
Regarding step S32, if the primitive under consideration is a point, then clipping passes the primitive unchanged if the primitive lies within the clip volume; otherwise, the primitive is discarded. If the primitive is a line segment at step S30, then clipping does nothing to the primitive if the primitive lies entirely within the clip volume and discards the primitive if it lies entirely outside the volume. If part of the line segment lies in the volume and part lies outside, then the line segment is clipped and new vertex coordinates are computed for one or both vertices. A clipped line segment endpoint lies on both the original line segment and the boundary of the clip volume.
The clipping process at step S40 yields a value, 0≦t≦1, for each clipped vertex. If the coordinates of a clipped vertex are D and the original vertices' coordinates are D1 and D2, then t is given byD=tD1+(1+t)D2 where the value of t is used in color and texture coordinate clipping etc.
If the primitive is a polygon at step S28, then the primitive is passed if every one of its edges lies entirely inside the clip volume and is either clipped or discarded otherwise. Polygon clipping may cause polygon edges to be clipped, but because polygon connectivity must be maintained, these clipped edges are connected by new edges that lie along the clip volume's boundary. Thus, clipping may require the introduction of new vertices into a polygon. Edge flags are associated with these vertices so that edges introduced by clipping are flagged as boundaries (edge flag TRUE), and so that original edges of the polygon that become cut off at these vertices retain their original flags.
If it happens that a polygon intersects an edge of the clip volume's boundary, then the clipped polygon must include a point on this boundary edge. This point must lie in the intersection of the boundary edge and the convex hull of the vertices of the original polygon.
A line segment or polygon whose vertices have wc values of differing signs may generate multiple connected components after clipping. Some implementations are not required to handle this situation. That is, only the portion of the primitive that lies in the region of wc>0 need be produced by clipping.
Primitives rendered with clip planes must satisfy a complementarily criterion. Suppose a single clip plane with coefficients (p′1 p′2 p′3 p′4) (or a number of similarly specified clip planes) is enabled and a series of primitives are drawn. Next, suppose that the original clip plane is re-specified with coefficients (−p′1 −p′2 −p′3 −p′4) (and correspondingly for any other clip planes) and the primitives are drawn again. In this case, primitives must not be missing any pixels, nor may any pixels be drawn twice in regions where those primitives are cut by the clip planes.
Clipping requires plane equations (each consisting of four single-precision floating-point coefficients) and corresponding bits indicating which of these user-defined plane equations are enabled. In the initial state, all user-defined plane equation coefficients are zero and all planes are disabled.
In view of the above description of the user-defined clipping process in eye space, there is a need to reduce the computations for user-defined clipping in 3D imaging devices having a 3D graphics software and/or hardware engine.
There is also a need to perform the user-defined clipping in the object space to avoid transforming vertices from the object space into the eye space. Most cases in 3D gaming content processing require less computation to transform a few user-defined clip planes from the eye space to the object space than to transform a lot of vertices from the object space to the eye space.
Furthermore, there is a need to avoiding generation of eye coordinates if lighting is disabled.